{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def readBinaryWatch(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        base = {\n",
    "            1:1,\n",
    "            2:2,\n",
    "            3:4,\n",
    "            4:8,\n",
    "            5:16,\n",
    "            6:32}\n",
    "        \n",
    "        time_dict = {}\n",
    "        time_list = []\n",
    "        \n",
    "        def genTime(hour_base, minute_base, hour, minute, n):\n",
    "            if n < 0:\n",
    "                return\n",
    "            if hour > 11:\n",
    "                return\n",
    "            if minute > 59:\n",
    "                return            \n",
    "            if n == 0:\n",
    "                if minute < 10:\n",
    "                    time = str(hour) + \":0\" + str(minute)\n",
    "                else:\n",
    "                    time = str(hour) + \":\" + str(minute)\n",
    "                    \n",
    "                if time not in time_dict:\n",
    "                    time_dict[time] = True\n",
    "                    time_list.append(time)\n",
    "                return\n",
    "            \n",
    "            for i in range(hour_base, 5):\n",
    "                for j in range(minute_base, 7):\n",
    "                    if i == hour_base and j == minute_base:\n",
    "                        continue\n",
    "                    if i == hour_base:\n",
    "                        genTime(hour_base, j, hour, minute+base[j], n - 1)\n",
    "                        continue\n",
    "                    if j == minute_base:\n",
    "                        genTime(i, minute_base, hour+base[i], minute, n - 1)\n",
    "            return\n",
    "        \n",
    "        genTime(0,0,0,0,num)\n",
    "        \n",
    "        return time_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:03',\n",
       " '0:05',\n",
       " '0:09',\n",
       " '0:17',\n",
       " '0:33',\n",
       " '1:01',\n",
       " '2:01',\n",
       " '4:01',\n",
       " '8:01',\n",
       " '0:06',\n",
       " '0:10',\n",
       " '0:18',\n",
       " '0:34',\n",
       " '1:02',\n",
       " '2:02',\n",
       " '4:02',\n",
       " '8:02',\n",
       " '0:12',\n",
       " '0:20',\n",
       " '0:36',\n",
       " '1:04',\n",
       " '2:04',\n",
       " '4:04',\n",
       " '8:04',\n",
       " '0:24',\n",
       " '0:40',\n",
       " '1:08',\n",
       " '2:08',\n",
       " '4:08',\n",
       " '8:08',\n",
       " '0:48',\n",
       " '1:16',\n",
       " '2:16',\n",
       " '4:16',\n",
       " '8:16',\n",
       " '1:32',\n",
       " '2:32',\n",
       " '4:32',\n",
       " '8:32',\n",
       " '3:00',\n",
       " '5:00',\n",
       " '9:00',\n",
       " '6:00',\n",
       " '10:00']"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.readBinaryWatch(2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
